/*
 * The RNC unpacker library is copyright Alexander Gitter. It is released
 * under a BSD license.
 */

package utils.dernc;

import java.io.IOException;

/**
 * A Java implementation of the RNC decompression algorithm.
 * 
 * @author Alexander Gitter
 */
public class DeRNC {
	public static byte[] main_unpack(byte[] packedBytes) throws InvalidRNCArchiveException, IOException {
		if (packedBytes[0] != 'R' || packedBytes[1] != 'N' || packedBytes[2] != 'C') {
			throw new InvalidRNCArchiveException();
		}
		CharPointer pp = new CharPointer(packedBytes);
		int ulen = rnc_ulen(pp);
		byte unpacked[] = new byte[ulen];
		rnc_unpack(pp, new CharPointer(unpacked));
		return unpacked;
	}

	/**
	 * Return the uncompressed length of a packed data block, or a negative
	 * error code.
	 */
	protected static int rnc_ulen(CharPointer p) throws IllegalArgumentException {
		return blong(new CharPointer(p, 4));
	}

	protected static void rnc_unpack(CharPointer input, CharPointer output) throws IOException {
		input.inc(18);
		BitStream bis = new BitStream(input);
		// CRC-Check should be done here
		bis.bit_advance(2, input);
		while (output.pos() < output.len()) {
			Huftable raw = new Huftable();
			raw.read(bis, input);
			Huftable dist = new Huftable();
			dist.read(bis, input);
			Huftable len = new Huftable();
			len.read(bis, input);
			int ch_count = bis.bit_read(0xFFFF, 16, input);
			while (true) {
				int length, posn;
				length = raw.huf_read(bis, input);
				if (length < 0) {
					throw new IOException();
				}
				if (length > 0) {
					while (length-- > 0) {
						output.set(input.get());
						output.inc();
						input.inc();
					}
					bis.bitread_fix(input);
				}
				if (--ch_count <= 0) {
					break;
				}
				posn = dist.huf_read(bis, input);
				if (posn == -1) {
					throw new IOException();
				}
				length = len.huf_read(bis, input);
				if (length == -1) {
					throw new IOException();
				}
				posn += 1;
				length += 2;
				while (length-- > 0) {
					output.set(output.get(-posn));
					output.inc();
				}
			}
		}
		if (output.pos() > output.len()) {
			throw new IOException();
		}
		// CRC unpacked data
	}

	/**
	 * Return the big-endian longword at p.
	 */
	protected static int blong(CharPointer p) {
		int n;
		n = p.get(0);
		n = (n << 8) | p.get(1);
		n = (n << 8) | p.get(2);
		n = (n << 8) | p.get(3);
		return n;
	}

	/**
	 * Return the little-endian word at p.
	 */
	protected static int lword(CharPointer p) {
		int n;
		n = p.get(1);
		n = (n << 8) | p.get(0);
		return n;
	}
}

class BitStream {
	private int buffer;
	private int count;

	public BitStream(CharPointer p) {
		this.buffer = DeRNC.lword(p);
		this.count = 16;
	}

	/**
	 * Returns some bits.
	 */
	int bit_peek(int mask) {
		return this.buffer & mask;
	}

	/**
	 * Advances the bit stream.
	 */
	void bit_advance(int n, CharPointer p) {
		this.buffer >>>= n;
		this.count -= n;
		if (this.count < 16) {
			p.inc(2);
			this.buffer |= (DeRNC.lword(p) << this.count);
			this.count += 16;
		}
	}

	/**
	 * Reads some bits in one go (ie the above two routines combined).
	 */
	int bit_read(int mask, int n, CharPointer p) {
		int result = bit_peek(mask);
		bit_advance(n, p);
		return result;
	}

	/**
	 * Fixes up a bit stream after literals have been read out of the data
	 * stream.
	 */
	void bitread_fix(CharPointer p) {
		this.count -= 16;
		// Remove the top 16 bits
		this.buffer &= (1 << this.count) - 1;
		// Replace with what's at *p
		this.buffer |= (DeRNC.lword(p) << this.count);
		this.count += 16;
	}
}

class Huftable {
	int num;
	long code[] = new long[32];
	int codelen[] = new int[32];
	int value[] = new int[32];

	void read(BitStream bis, CharPointer p) {
		int i, j, k, num;
		int leaflen[] = new int[32];
		int leafmax;
		long codeb;
		num = bis.bit_read(0x1f, 5, p);
		if (num < 1) {
			return;
		}
		leafmax = 1;
		for (i = 0; i < num; ++i) {
			leaflen[i] = bis.bit_read(0x0F, 4, p);
			if (leafmax < leaflen[i]) {
				leafmax = leaflen[i];
			}
		}
		codeb = 0L;
		k = 0;
		for (i = 1; i <= leafmax; i++) {
			for (j = 0; j < num; j++) {
				if (leaflen[j] == i) {
					this.code[k] = mirror(codeb, i);
					this.codelen[k] = i;
					this.value[k] = j;
					codeb++;
					k++;
				}
			}
			codeb <<= 1;
		}
		this.num = k;
	}

	/**
	 * Read a value out of the bit stream using the given Huffman table.
	 */
	int huf_read(BitStream bs, CharPointer p) {
		int i;
		int val;
		for (i = 0; i < this.num; i++) {
			int mask = (1 << this.codelen[i]) - 1;
			if (bs.bit_peek(mask) == this.code[i]) {
				break;
			}
		}
		if (i == this.num) {
			return -1;
		}
		bs.bit_advance(this.codelen[i], p);
		val = this.value[i];
		if (val >= 2) {
			val = 1 << (val - 1);
			val |= bs.bit_read(val - 1, this.value[i] - 1, p);
		}
		return val;
	}

	long mirror(long x, int n) {
		long top = 1 << (n - 1), bottom = 1;
		while (top > bottom) {
			long mask = top | bottom;
			long masked = x & mask;
			if (masked != 0 && masked != mask) {
				x ^= mask;
			}
			top >>>= 1;
			bottom <<= 1;
		}
		return x;
	}
}

class CharPointer {
	private byte[] data;
	private int pos;

	CharPointer(byte[] data) {
		this.data = data;
		this.pos = 0;
	}

	CharPointer(byte[] data, int pos) {
		this.data = data;
		this.pos = pos;
	}

	CharPointer(CharPointer c) {
		this.data = c.data;
		this.pos = c.pos;
	}

	CharPointer(CharPointer c, int offset) {
		this.data = c.data;
		this.pos = c.pos + offset;
	}

	void set(int b) {
		this.data[this.pos] = (byte) (0xff & b);
	}

	void set(int b, int offset) {
		this.data[this.pos + offset] = (byte) (0xff & b);
	}

	int get() {
		return (this.data[this.pos] & 0xff);
	}

	int get(int offset) {
		if (this.pos + offset >= this.data.length) { // Hack!!
			return 0;
		} else {
			return (this.data[this.pos + offset] & 0xff);
		}
	}

	void inc() {
		this.pos++;
	}

	void inc(int offset) {
		this.pos += offset;
	}

	int pos() {
		return this.pos;
	}

	int len() {
		return this.data.length;
	}
}
